Many problems arising in the sciences and engineering fields can be reduced to the study of the properties of certain combinatorial objects. For instance natural or artificial networks are usually modelled as labelled (vertices and/or arcs) graphs or digraphs. Many patents have been granted for methods of solving problems on graphs or digraphs. As a non exhaustive sample: U.S. Pat. No. 6,438,734; U.S. Pat. No. 6,674,757; U.S. Pat. No. 7,298,704.
Within all digraph problems the well-known problem of finding a hamiltonian traversal (from now on HT, referring both to a hamiltonian cycle or a hamiltonian path) is of interest for theoretical and practical purposes. A hamiltonian path is a path in the digraph which passes trough all the vertices only once. A hamiltonian cycle is a hamiltonian path where the ending vertex is adjacent to the starting vertex. For many applications the possibility of solving efficiently the decision, searching (of one, several or all), optimization and counting versions of the hamiltonian traversals of a given digraph (this is the hamiltonian problem or from now on HP) is a highly desirable property. But this problem even when restricted to the decision version being one of the classical NP-complete problems (for general digraphs and graphs) we should not expect to find a worst-case efficient solution to it. U.S. Pat. No. 6,636,840 has been granted for a computer system designed specifically to solve the optimization hamiltonian cycle problem in a weighted digraph.
Although it is known that in the average-case and random settings the decision HT problem is feasible, it is interesting for specific classes of structured digraphs which appears in practical applications to develop more efficient methods of solving it than those available for the general random or average-case. Within all digraphs, an efficient solution to the HP in vertex-transitive digraphs is of interest in some engineering areas such as the field of interconnection networks design (for details see two papers form Wenjun Xiao and Behrooz Parhami, “Some mathematical properties of Cayley digraphs with applications to interconnection network design 2005 and 2007” in the International Journal of Computer Mathematics, Vol 182, no 5, May 2005, p521-528 and “Structural properties of Cayley digraphs with applications to mesh and pruned torus interconnection networks”, Journal of Computer and System Sciences 73, (2007), p1232-1239; and J. Duato, Ni Lionel and Yalamanchili Sudhakar book “Interconnection Networks: an engineering approach, Morgan Kauffman, 2003). Most vertex-transitive digraphs in applications are Cayley digraphs. Up to now it has neither been proved that the HP for Cayley digraphs is NP-Complete nor it is known a deterministic polynomial time general procedure which solves it, so the computational complexity of this problem remains unknown (for details see Ramyaa Master of Science thesis “Finding hamilton cycles in cubic digraphs and restricted Cayley digraphs” University of Georgia, 2004). An US patent related with hamiltonian cycles in structured graphs (hypercubes) is U.S. Pat. No. 2,632,058 issued in 1953.
Since when designing a network for practical applications low vertex degree is a desirable property, considerable effort from skilled artisans has been devoted to the most restricted class of the 2-generated Cayley digraphs, but the best known general method valid for this restricted cases uses backtracking, which is exponential in time in the worst case (for details see S. Effler Master of Science thesis “Enumeration, Isomorphism and hamiltonicity of Cayley digraphs: cubic and 2-generated, University of Victoria, Canada, 2002) and therefore is able to solve HT problem only small Cayley networks (for example, a solution for many networks of size 720 are still unknown, Effler, 2002 op. cit.). For some special cases of this restricted class though, deterministic polynomial time decision, searching and counting procedures are known (for details see Qi Fan Yang, R. E Burkard, E. Cela and G. J. Woeginger, “Hamiltonian cycles in circulant digraphs in two stripes”, Discrete Mathematics 176, (1997), p 233-254) and for some other cases a polynomial time decision procedure is known (for details see S. J. Curran and J. A. Gallian “Hamiltonian cycles in Cayley graphs and digraphs: a survey”, Discrete Mathematics 156, (1996), p 1-18). Most of this polynomial time decision and/or searching procedures relates to Cayley digraphs of commutative groups or structurally close to commutative such as metacyclic groups. The decision problem restricted to all 2-generated Cayley digraphs of the symmetric group or alternating groups (which are widely used in practical applications such as interconnection networks), or even when restricted to a very specific infinite family is considered as a hard problems (for details see I.Pak and R.Radoicic, “Hamilton cycles in Cayley graphs”, Preprint available at the www, (2004) and D. Knuth “The Art of computer programming”, Vol 4, 7.1.2., Draft). In fact the hamiltonian decision problem for general (unstructured) 2 in-2 out digraphs is NP-complete as proved by Plesnik (unpublished result available at www) in the late seventies.
The best obvious algorithm for searching an HT in the general case of 2-generated Cayley digraphs has a worst case time complexity of O(2^(|G|/order(−xy)).
Some variations of this general exponential best algorithm, introducing some changes has been presented for cases where at least one of the generators is an involution (for details see Ramyaa, op. cit. 2004), obtaining as a result a heuristic procedure which might yield or not a correct result. In other non-commutative cases improved backtracking procedures has been implemented; but this method needs previous ad-hoc hand analysis by the designer for each case (for details see a note form F. Ruskey, Ming Tian and A. Weston, “The hamiltonicity of directed cayley digraphs and graphs or a tale of backtracking”, in Discrete Applied Mathematics 57, (1995), p75-83). In all this cases, like with other structured objects or the skilled artisan is able to take advantage of its structure or widely used methods (deterministic with time or iteration limits, greedy, random, heuristic) will fail (Ramyaa, op.cit. 2004).
In the field of computer architecture the interconnection network is now considered as one of the key elements of a computer together with the memory, processor or input/output components (for details see Behrooz Parhami book “Computer Architecture: from microprocessors to supercomputers, Oxford University Press, 2005); when the number of components of these key elements increases (number of processors, number of memory positions, number of input or output elements), the best option to connect them is through an interconnection network; many interconnection networks are modelled as Cayley digraphs and hamiltonicity (together with a fixed low degree, low diameter and large bisection width) is one of its desired properties; the need of higher computational power requests more and more components in computer systems and therefore interconnection networks will have more and more nodes.
There exist then a need of a procedure which identifies which structural aspects of the digraphs are relevant for hamiltonicity and exploits this knowledge for improving the present general or specific methods for solving the decision, searching, counting and optimization versions of the hamiltonian traversal problem for Cayley digraphs and other vertex transitive networks. As any skilled artisan knows all the versions of the problem are requested for practical purposes.